package leetcode_jz_offer.day23;

import java.util.HashMap;
import java.util.Map;

/**
 * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 **/
public class Num39_数组中出现次数超过一半的数字 {
//    public int majorityElement(int[] nums) {
//        Map<Integer,Integer> map=new HashMap<>();
//        int maxCount=0;//获取map集合的最大value
//        int res=0;
//        for (int i = 0; i < nums.length; i++) {
//            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
//            maxCount=maxCount>map.get(nums[i])?maxCount:map.get(nums[i]);
//        }
//        for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
//            if(maxCount==entry.getValue()){
//                res=entry.getKey();
//            }
//        }
//        return maxCount>nums.length/2?res:0;
//    }

    //摩尔投票法解决
    public int majorityElement(int[] nums) {
        if(nums==null||nums.length==0){
            return 0;
        }
        int target=nums[0];
        int times=1;
        for (int i = 1; i < nums.length; i++) {
            if(times==0){
                //票数归零，换候选人
                target=nums[i];
            }
            if(target==nums[i]){
                times++;
            }else {
                times--;
            }
        }
        //已经找出候选人target，现在重新统计该候选人的票数
        times=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==target){
                times++;
            }
        }
        //票数统计完毕，看是否超过一半，超过一半才能返回target
        return times>nums.length/2?target:0;
    }
}
